package io.zhengsh.vvip.leetcode.findandsort;

import java.util.ArrayList;
import java.util.List;

/**
 * 57. 插入集合
 */
public class Q57_Insert_Interval {

    class Solution {
        public int[][] insert(int[][] intervals, int[] newInterval) {
            int left = newInterval[0], right = newInterval[1];
            boolean placed = false;
            List<int[]> resultList = new ArrayList<>();

            for (int[] interval : intervals) {
                if (interval[0] > right) {
                    // 在插入区间的右侧且无交集
                    if (!placed) {
                        resultList.add(new int[]{left, right});
                        placed = true;
                    }
                    resultList.add(interval);
                } else if (interval[1] < left) {
                    // 在插入区间的左侧且无交集
                    resultList.add(interval);
                } else {
                    // 与插入区间有交集，计算他们的并集
                    left = Math.min(left, interval[0]);
                    right = Math.max(right, interval[1]);
                }
            }
            if (!placed) {
                resultList.add(new int[]{left, right});
            }
            return resultList.toArray(new int[resultList.size()][]);
        }
    }

}
